home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Shareware Overload Trio 2
/
Shareware Overload Trio Volume 2 (Chestnut CD-ROM).ISO
/
dir33
/
stac-ms.zip
/
MS-SUIT
< prev
Wrap
Text File
|
1993-02-03
|
8KB
|
180 lines
BBS: CCCBBS Conference: Modems Imported: 2/03/1993
To: ALL Num: 1287 Date: 2/03/1993
From: ROSS WILLIAMS Re: 0 Time: 6:07 am
Subj: MS-DOS 6 patent suit: Cal Prvt: N Read: N
Dear Netters,
As many of you may know by now, Microsoft is being sued by Stac
Electronics who claim infringement of a data compression software
patent. The patent is US Patent #4,701,745, the "Waterworth" patent,
and has a priority date of 6 March 1985. Its abstract and claims
sections appear at the end of this posting.
MS-DOS 6, due to be released in the first half of 1993, is the target
of the Stac suit. MS-DOS 6 contains transparent disk compression, a
key component of which is the data compression algorithm under
dispute.
It's not hard to work out WHY this patent lawsuit exists. By
incorporating transparent disk compression into MS-DOS, Microsoft
will, for the first time, be competing directly with third-party
transparent disk compression products, and this is likely to
precipitate a shake-out in the niche. This filtering down from third
party products to the operating system is a natural progression in
technological development, and should be applauded (encryption is
probably next in line). However, it must be extremely threatening to
companies such as Stac Electronics who live in this transitory niche.
The patent turns out to be rather significant in a number of ways. Not
only is it a very early software patent (1985), but it actually seems
to cover most of the content of a LATER patent --- the "Gibson and
Graybill" patent #5,049,881 (registered in 1990) --- so recently
fought over by Intersecting Concepts and AdStor. This makes the
Waterworth patent the king pin of a small tree of patents.
Having myself re-invented and published in 1989-1991 an algorithm (my
LZRW1 algorithm) very similar to that described in the Waterworth
patent, I am completely convinced of the patent's triviality. In a
nutshell, the patent covers the use of hashing to find matches in a
sliding input window. This is a fundamental and obvious technique in
data compression and it is ludicrous that it should be anywhere but in
the public domain. In fact it is ludicrous that it should have ever
even existed as a piece of intellectual property.
The fact that a company as large as Microsoft is defendent in this
case means that the stakes are high. If Microsoft wins then the whole
tree of patents will fall. If Microsoft loses then it is unlikely that
the patent will be challenged again and, as a consequence, it will be
massively strengthened. I believe that it is in the interests of all
those involved with data compression (except of course you know who)
to see that this patent is toppled.
Because of my close involvement with these kinds of algorithms, and my
sympathy with their cause in this instance, Microsoft is employing me
on a contract basis to assist with the case. Currently I am collecting
prior art. If you know of any prior art, or have any idea of where it
might be obtained, I would be most grateful if you could contact me at
the email address below.
Thanks,
Ross Williams
ross@spam.adelaide.edu.au
--<Start of Patent Abstract and Claims>--
UNITED STATES PATENT [19] [11] Patent Number 4,701,745
Waterworth [45] Date of Patent: Oct 20, 1987
------------------------------------------------------------------
[54] DATA COMPRESSION PATENT
[75] Inventor: John R. Waterworth,
Cheadle, England.
[73] Assignee: Ferranti, plc, Cheshire, England
[21] Appl. No.: 835,793
[22] Filed: Mar.3, 1986
[30] Foreign Application Priority Data
Mar.6, 1985 [GB] United Kingdom.....8505790
[51] Int Cl.^4 .................H03M 7/30
[52] U.S. Cl. ................340/347 DD; 364/900
[58] Field of Search......... 340/347 DD; 235/310;
358/260, 261; 364/900
[56] References Cited
U.S. PATENT DOCUMENTS
4,054,951 10/1977 Jackson.......364/900
Primary Examiner ---- Charles D. Miller
Attorney, Agent, or Firm --- Kerkam, Stowell, Kondracki & Clarke
[57] ABSTRACT
A data compression system includes an input store (1) for receiving
and storing a plurality of bytes of data from an outside source. Data
processing means for processing successive bytes of data from the
input store includes circuit means (21-25) operable to check whether
a sequence of bytes is identical with a sequence of bytes already
processed, output means (27) operable to apply to a transfer medium
(12) each byte of data not forming part of such an identical sequence,
and an encoder (26) responsive to the identification of such a
sequence to apply to the transfer means (12) an identification signal
which identifies both the location in the input store of the previous
occurrence of the sequence of bytes and the number of bytes in the
sequence.
8 Claims, 7 Drawing Figures
CLAIMS SECTION
--------------
I claim:
1. A data compression system comprising an input store for receiving
and storing a plurality of bytes of uncompressed data from an outside
source, and data processing means for processing successive bytes of
data from the input store;
the data processing means including circuit means operable to check
whether a sequence of successive bytes to be processed identical with
a sequence of bytes already processed, and including hash generating
means responsive to the application of a preedetermined number of
bytes in sequence to derive a hash code appropriate to those bytes, a
temporary store in which the hash code may represent the address of a
storage location, and a pointer counter operable to store in the
temporary store at said address a pointer indicative of the position
in the input store of one of the predetermined number of bytes;
output means operable to apply to a transfer medium each byte of data
not forming part of such an identical sequence; and
encoding means responsive to the identification of such a sequence to
apply to the transfer medium an identification signal which identifies
both the location in the input store of the previous occurrence of the
sequence of bytes and the number of bytes contained in the sequence.
2. A system as claimed in claim 1 in which the circuit means also
includes check means operable to check for identity between each of
the said predetermined number of bytes in sequence and each of a
similar sequence of bytes contained in the input store at a location
defined by a pointer read out from a temporary store at said address
and to check whether identity exists between suceeeding bytes in each
sequence of bytes, and a byte counter operable to count the number of
identical bytes in each sequence.
3. A system as claimed in claim 2 in which the encoder is operable
when such identity exists to encode the pointer read out from the
temporary store and the output of the byte counter.
4. A system as claimed in 1 which includes a plurality of input
stores each of which contains part only of the data from the
outside source.
5. A data comprtession system as claimed in claim 1 which includes
data receiving means operable to receive compressed data from the
transfer medium, an output store operable to store any uncompressed
byte of data received by the receiving means, and copying means
responsive to an identification signal to apply to the ouput store
the sequence of bytes already contained in said output store and
identified by the said identification signal, the arrangement being
such that the data contained in the output store is the exact
reconstruction of that applied at some earlier time to the input
store.
6. A system as claimed in claim 5 in which the data receiving means
includes a decoder means operable to separate uncompressed bytes of
data from identification signals.
7. A system as claimed in claim 1 in which the transfer
medium comprises a communications channel between two spaced
locations.
8. A system as claimed in claim 1 in which the transfer medium
comprises a data storage medium.
* * * * *
--<End of Patent Abstract and Claims>--